#define  _CRT_SECURE_NO_WARNINGS 1


#include "BinaryTree.h"
#include "Queue.h"

BTNode* BuyTreeNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	newnode->data = x;
	newnode->left = newnode->right = NULL;

	return newnode;
}


BTNode* CreatTree(BTDataType* arr, int* pi)
{
	BTNode* root = NULL;
	if (arr[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	else
	{
		root = BuyTreeNode(arr[(*pi)++]);
		root->left = CreatTree(arr, pi);
		root->right = CreatTree(arr, pi);
	}

	return root;
}


void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		printf("%c ", root->data);
		PreOrder(root->left);
		PreOrder(root->right);
	}
}


void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		InOrder(root->left);
		printf("%c ", root->data);
		InOrder(root->right);
	}
}


void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%c ", root->data);
	}
}


void LevelOrder(BTNode* root)
{
	QU Qu;
	QueueInit(&Qu);
	if(root)
	QueuePush(&Qu, root);
	while (!QueueEmpty(&Qu))
	{
		BTNode* ret = QueueFront(&Qu);
		printf("%c ", ret->data);
		QueuePop(&Qu);
		if (ret->left)
			QueuePush(&Qu, ret->left);
		if (ret->right)
			QueuePush(&Qu, ret->right);
	}
}


int TreeNodeSize(BTNode* root)
{
	return root == NULL ? 0 : 1 + TreeNodeSize(root->left) + TreeNodeSize(root->right);
}


int LeafNodeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else if (root->left == NULL && root->right == NULL)
		return 1;
	else
	{
		return LeafNodeSize(root->left) + LeafNodeSize(root->right);
	}
}


int MaxDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
	{
		int ld = MaxDepth(root->left);
		int rd = MaxDepth(root->right);

		return 1 + (ld > rd ? ld : rd);
	}
}


int MinDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	else if (root->left == NULL)
		return 1 + MinDepth(root->right);
	else if (root->right == NULL)
		return 1 + MinDepth(root->left);
	else
	{
		int ld = MinDepth(root->left);
		int rd = MinDepth(root->right);

		return 1 + (ld > rd ? rd : ld);
	}

}


bool IsBalance(BTNode* root)
{
	if (root == NULL)
		return true;
	else
	{
		return abs(MaxDepth(root->left) - MaxDepth(root->right)) < 2 &&
			IsBalance(root->left) &&
			IsBalance(root->right);
	}
}